/*
https://leetcode-cn.com/problems/shortest-subarray-with-sum-at-least-k/solution/he-zhi-shao-wei-k-de-zui-duan-zi-shu-zu-by-leetcod/
 */
import java.util.Deque;
import java.util.LinkedList;

public class Solution862 {
    public int shortestSubarray(int[] nums, int k) {
        long[] sum=new long[nums.length+1];
        for (int i=1;i<=nums.length;i++){
            sum[i]=sum[i-1]+nums[i-1];
        }
        int ans=nums.length+1;
        Deque<Integer> deque=new LinkedList<>();
        for (int i=0;i<=nums.length;i++){
            while (!deque.isEmpty() && sum[i]<=sum[deque.getLast()]){
                deque.removeLast();
            }
            while (!deque.isEmpty() && sum[i]>=sum[deque.getFirst()]+k){
                ans=Math.min(ans,i-deque.removeFirst());
            }
            deque.addLast(i);
        }
        return ans==nums.length+1?-1:ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution862().shortestSubarray(new int[]{2,-1,2},3));
    }
}
